/*
 * @lc app=leetcode.cn id=516 lang=typescript
 *
 * [516] 最长回文子序列
 */

// @lc code=start
function longestPalindromeSubseq(s: string): number {
  const m = s.length;
  // dp[i][j]表示[i,j]区间内最长回文长度
  const dp = new Array(m).fill(0).map((_) => new Array(m).fill(0));

  for (let i = m - 1; i >= 0; i--) {
    // 单个字符一定是回文，长度为1
    dp[i][i] = 1;
    const ci = s[i];
    for (let j = i + 1; j < m; j++) {
      const cj = s[j];
      if (ci === cj) {
        // 首尾字符相等，可以根[i+1,j-1]连成新的回文
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        // 首尾不相等，取[i+1,j]和[i,j-1]区间的最大长度
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[0][m - 1];
}
// @lc code=end
